package com.xinpan.exercise;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Permutations2 {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Map<Integer, Integer> nCnt = new HashMap<Integer, Integer>();
        for(int i = 0; i < num.length; i++)
        {
            if(nCnt.get(num[i]) == null)
                nCnt.put(num[i], 1);
            else
                nCnt.put(num[i], nCnt.get(num[i])+1);
        }
        int nu = factorial(num.length);
        int de = 1;
        for(Integer val : nCnt.values())
            de *= factorial(val);
        int cnt = nu / de;
        
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        res.add(toList(num));
        
        for(int i = 1; i < cnt; i++)
        {
            nextPermutation(num);
            res.add(toList(num));
        }
        return res;
    }
    
    public ArrayList<Integer> toList(int[] num)
    {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i = 0; i < num.length; i++)
            arr.add(num[i]);
        return arr;
    }
    
    public int factorial(int n)
    {
        int res = 1;
        while(n > 0) res *= n--;
        return res;
    }
    
    public void nextPermutation(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(num.length <= 1)
            return;
        
        boolean ex = false;
        int i = num.length-1;
        for(; i > 0; i--)
        {
            if(num[i] > num[i-1])
            {
                ex = true;
                break;
            }
        }
        if(ex)
        {
            int j = i;
            for(; j < num.length; j++)
            {
                if(num[j] <= num[i-1])
                    break;
            }
            j--;
        
            int tmp = num[j];
            num[j] = num[i-1];
            num[i-1] = tmp;
        }

        
        int e = num.length-1;
        int s = i;
        while(s < e)
        {
            int tmp = num[e];
            num[e] = num[s];
            num[s] = tmp;
            s++;
            e--;
        }
    }
}
